package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/15.
 * 请实现一个函数，用来判断一颗二叉树是不是对称的。
 * 注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
 */
public class SymmetricalTree {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
/**
 * 想一下打印输出某二叉树的镜像，实现的思路是：
 * 采用层序遍历的思路对每一个遍历的节点，如果其有孩子节点，那么就交换两者。
 * 直到遍历的节点没有孩子节点为止，然而此题是对二叉树木镜像的判断，明显是更简单的，
 * 只需要进行两个判断：对节点的左孩子与其兄弟节点右孩子的判断以及对节点右孩子与其兄弟节点左孩子的判断。
 * 这样就完成对对一棵二叉树是否对称的判断。
 * */
    boolean isSymmetrical(TreeNode pRoot){
        if (pRoot == null) return true;
        return isSymmetricalCore(pRoot.left, pRoot.right);
    }

    private boolean isSymmetricalCore(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val == right.val)
            return isSymmetricalCore(left.left, right.right) && isSymmetricalCore(left.right, right.left);
        return false;
    }
}
